package 数据结构系列;

import org.w3c.dom.html.HTMLHeadElement;

public class 反转链表II_92 {
    class ListNode {
        int val;
        反转链表II_92.ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, 反转链表II_92.ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    ListNode successor = null;//后驱节点

    /*
    反转链表中的前n个节点
    */
    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {//经过下面的递归，一定会来到这里，把后驱节点赋上值。
            successor = head.next;//记录反转后的头节点 后面原来连接的那个节点
            return head;//反转一个节点，就是它自己
        }
        //以head.next为起点，需要反转前n-1个节点
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        head.next = successor;
        return last;
    }


    public ListNode reverseBetween(ListNode head, int m, int n) {

        if (head == null || head.next == null) {
            return head;
        }

        //base case  经过递归最终会来到这里的。
        if (m == 1) {//left=1,相当于链表开头的right个元素
            return reverseN(head, n);
        }

        /*对于head.next来说就是反转区间[left-1,right-1]
        reverseBetween();会返回反转后的链表头节点，head.next就是把反转后的头节点和head连接起来

         前进到反转的起点触发 base case
         */
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }
}
